package dp

func canPartition(nums []int) bool {
    dp := make([]int, 10001)
	dp[0] = 0
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum += nums[i]
	}
	if sum % 2 != 0 {
		return false
	}
	target := sum / 2
	for i := 0; i < len(nums); i++ {
		for j := target; j >= nums[i]; j-- {
			dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
		}
	}
	return dp[target] == target
}